Database systems use locks to maintain the consistency of databases when multiple users are accessing the same data at the same time. Before a transaction acquires dependency on the current state of a piece of data, such as by reading or modifying the data, the transaction must protect itself from the effects of another transaction modifying the same data. The transaction may request a lock on the data. The transaction holds the lock protecting the modification until the end of the transaction. Locks held by a transaction are released when the transaction completes (either commits or rollbacks).
Hierarchical locking is widely used in database indexes. Hierarchical locking lets large transactions take large (and thus few) locks and lets many small transactions proceed concurrently by taking small locks. The standard lock hierarchy for B-tree indexes starts by locking the table or view, then may lock the index or an index partition, and finally may lock a leaf page or individual key.
With the advent of disk drives approaching 1 Terabyte as well as very large databases and indexes, traditional hierarchical locking schemes begin to show flaws. For example, the current step from locking an index to locking its individual leaf pages or keys might prove too large. There may be millions of leaf pages and billions of keys in an index. Thus, if a lock on an entire index is too large and too restrictive for other transactions, thousands and maybe millions of individual locks are required. Conversely, if a transaction already holds 10,000 locks and then escalates to an index lock to save on computing resources, this index lock might inhibit hundreds of concurrent transactions. Current hierarchical locking schemes create a dilemma between locking an entire index and locking millions of individual leaf pages or keys.